/* 
  二路快排
  解决了当数组都是相同元素的时候，快排退化成O(n^2)时间复杂度的算法
  思路，引进i,j
  那么arr[l+1, i] <= arr[l]
  arr[j, r] >= arr[l]
  对于指针i++，当找到一个元素大于arr[l]就停下来
  对于指针j--，当找到一个元素小于arr[l]就停下来
  然后两个交换位置，交换完位置后，i++,j--
  当i=j的时候，说明指向同一个元素，且这个元素=arr[l]
  当i>=j的时候，说明已经比较完毕，且此时arr[j]<=arr[l]的元素（因为它会j--，回到上个循环中
  arr[i]的位置，所以此时arr[j]<=arr[l]）
  上面的递归结束后，swap(arr, l, j)的位置，且此时j就是分区点
*/

class QuickSort {
  static aaa() {
    console.log();
  }
  sort(arr) {
    this.quickSort(arr, 0, arr.length - 1);
  }
  quickSort(arr, l, r) {
    if (l >= r) {
      return;
    }
    // p左边的都是<= p,右边的都是>=p
    const p = this.partition(arr, l, r);
    this.quickSort(arr, l, p - 1);
    this.quickSort(arr, p + 1, r);
  }

  partition(arr, l, r) {
    // 二路快排 这里需要加一是因为初始的时候，还没有处理i,j上的元素
    // 保证：arr[l+1, i - 1] <= arr[l] arr[j + 1, r] >= arr[l]
    let tempPartition = Math.floor(Math.random() * (r - l + 1)) + l;
    this.swap(arr, l, tempPartition);
    let i = l + 1;
    let j = r;
    while (true) {
      while (i <= j && arr[i] < arr[l]) {
        // 寻找第一个大于arr[l]的值，并停在这个位置
        i++;
      }
      while (j >= i && arr[j] > arr[l]) {
        // 寻找第一个大于arr[l]的值，并停在这个位置
        j--;
      }
      if (i >= j) {
        // 说明已经比较完了
        break;
      }
      this.swap(arr, i, j);
      i++;
      j--;
    }
    // 此时需要和l交换位置
    this.swap(arr, l, j);
    return j;
  }

  swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}
function generateArr(num, end) {
  const arr = [];
  for (let i = 0; i < num; i++) {
    // eslint-disable-next-line no-unused-expressions
    arr[i] = Math.floor(Math.random() * end);
  }
  return arr;
}
const sort = new QuickSort();
const arr = generateArr(20, 100);
console.log(arr);
sort.sort(arr);
console.log(arr);
